题解 CF128D@洛谷 | 128D@Codeforces 【Numbers】

简单构造题。

题意：给定 $n$ 个数，是否能排成一圈，使相邻两个数差 $1$。

根据题意，为了使相邻两个数差 $1$，圆圈中 $+1$ 和 $-1$ 的次数必定相等才能组成闭环，因此 $n$ 必须是偶数，对于奇数可以直接输出无解（代码注释 {1}）。

然后同样根据相邻两个数差 $1$ 的性质，我们将原数列排序，枚举相邻两个下标的数，如果差大于 $1$ 也输出无解（代码注释 {2}）。

之后找到数列最小值，把每个数减去最小值再加 $1$，即可得到一串与原数列等效的、最小值为 $1$ 的数列，经过前面两个特判，可以保证最大值不超过 $10^5$。然后从最小值开始，可以 $+1$ 时选择 $+1$，否则看看是否可以 $-1$，若不可以就跳出循环。

由于闭环性质，要形成环则最后一个数必定是 $2$，如果不是 $2$ 则不能成环，输出无解（代码注释 {3}）。

否则将整个桶扫一遍，如果有地方不为 $0$ 则代表成环失败，实处物价（代码注释 {4}）。

否则即代表我们构造出了一个符合题意的环，输出有解即可。

这样就水过了一道 CF *2000 的构造题（

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const int N = 1e5+5, inf = 1e9;

int n, a[N], buc[N], mi = inf;

int main() {
	scanf("%d", &n);
	if(n & 1) return puts("NO"), 0; // {1}
	rep(i, 1, n) scanf("%d", &a[i]), mi = min(mi, a[i]);
	sort(a+1, a+1+n);
	rep(i, 2, n) if(a[i] - a[i-1] > 1) return puts("NO"), 0; // {2}
	rep(i, 1, n) ++buc[a[i]-mi+1];
	int u = 1; --buc[1];
	loop {
		if(buc[u+1]) --buc[++u];
		else if(buc[u-1]) --buc[--u];
		else break;
	}
	if(u != 2) return puts("NO"), 0; // {3}
	rep(i, 0, N-1) if(buc[i]) return puts("NO"), 0; // {4}
	return puts("YES"), 0;
}